/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/fast-power
   @Language: C++
   @Datetime: 16-02-09 05:49
   */

class Solution {
public:
	/**
	 * @param a: A 32bit integer
	 * @param b: A 32bit integer
	 * @param n: A 32bit integer
	 * @return: An integer
	 * Tip: a^n % b
	 */
	int fastPower(int a, int b, int n) {
		// write your code here
		if(n==0) return 1%b;
		int res=1;
		for(; n; n>>=1){
			if(n&1) res=(res*a)%b;
			a=(a*a)%b;
		}
		return res;
	}
};
